﻿// 资源结构层次

using System.Collections.Generic;
using LitJson;
using UnityEngine;

public class AssetBundleGraph
{
     public class GraphNode
    {
        public enum State
        {
            White = 0,
            Gray = 1,
            Black = 2,
        }

        public LinkedList<string> names;
        public HashSet<GraphNode> children;
        public State state = State.White;

        public GraphNode(string name)
        {
            names = new LinkedList<string>();
            children = new HashSet<GraphNode>();

            names.AddLast(name);
        }

        public GraphNode(LinkedList<string> nameList, HashSet<GraphNode> nodeHash)
        {
            names = nameList;
            children = nodeHash;
        }

        public GraphNode(LinkedList<string> nameList)
        {
            names = nameList;
            children = new HashSet<GraphNode>();
        }

        public void AddChild(GraphNode child)
        {
            children.Add(child);
        }

        public void Add(GraphNode node)
        {
            foreach(var name in node.names)
            {
                names.AddLast(name);
            }

            foreach(var child in node.children)
            {
                children.Add(child);
            }
        }

        public string Name2String()
        {
            string msg = "(";
            foreach(var name in names)
            {
                msg += (name + ", ");
            }

            msg = msg.Substring(0, msg.Length - 2);
            msg += ")";

            return msg;
        }
    }

    private HashSet<GraphNode> nodes = new HashSet<GraphNode>();
    public HashSet<GraphNode> Nodes {
        get {
            return nodes;
        }
    }

    private static string NODES = "nodes";
    private static string NAMES = "names";
    private static string DEPENDENCIES = "dependencies";

    public AssetBundleGraph(AssetBundleManifest manifest)
    {
        Dictionary<string, GraphNode> nodeMap = new Dictionary<string, GraphNode>();

        foreach(string bundleName in manifest.GetAllAssetBundles())
        {
            nodeMap.Add(bundleName, new GraphNode(bundleName));
        }

        foreach(var kv in nodeMap)
        {
            string name = kv.Key;
            GraphNode node = kv.Value;

            foreach(string dep in manifest.GetDirectDependencies(name))
            {
                if (nodeMap.ContainsKey(dep))
                {
                    node.AddChild(nodeMap[dep]);
                }
            }

            nodes.Add(kv.Value);
        }
    }

    public string ToString(string msg = "Graph")
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder();

        sb.Append(msg);
        sb.Append(":\n");
        foreach(var node in nodes)
        {
            sb.Append("(");

            LinkedListNode<string> curr = node.names.First;
            while(curr != null)
            {
                if (curr == node.names.Last)
                {
                    sb.Append(curr.Value);
                }
                else
                {
                    sb.AppendFormat("{0},", curr.Value);
                }

                curr = curr.Next;
            }

            sb.Append(") => [");

            int count = node.children.Count;
            int idx = 0;
            foreach (var child in node.children)
            {
                sb.Append("(");
                curr = child.names.First;
                while(curr != null)
                {
                    if (curr == child.names.Last)
                    {
                        sb.Append(curr.Value);
                    }
                    else
                    {
                        sb.AppendFormat("{0}, ", curr.Value);
                    }

                    curr = curr.Next;
                }

                ++idx;

                if (idx < count)
                {
                    sb.Append("), ");
                }
            }

            sb.Append("]\n");
        }

        return sb.ToString();
    }

    public bool EliminateCycle()
    {
        bool cycled = false;
        while(eliminateOneCycle())
        {
            cycled = true;
        }

        return cycled;
    }

    bool eliminateOneCycle()
    {
        foreach(var node in nodes)
        {
            node.state = GraphNode.State.White;
        }

        bool cycled = false;
        GraphNode cycledNode = null;
        Stack<GraphNode> stack = null;

        // 检查子树中是否有资源重复引用的情况，父子结构相当于依赖关系，父节点依赖子节点
        // 算法的方式是以栈方式遍历树节点，如果依赖子节点中存在Gray状态，证明当前子树内部循环引用问题，在资源载入时会出现循环等待的异常，典型的死锁情况
        foreach(var node in nodes)
        {
            switch (node.state)
            {
                case GraphNode.State.White:
                    {
                        stack = new Stack<GraphNode>();
                        stack.Push(node);

                        while(stack.Count > 0 &&!cycled)
                        {
                            GraphNode n = stack.Peek();
                            switch (n.state)
                            {
                                case GraphNode.State.White:
                                case GraphNode.State.Gray:
                                    {
                                        if (n.children.Count == 0)
                                        {
                                            stack.Pop();
                                            n.state = GraphNode.State.Black;
                                        }
                                        else
                                        {
                                            bool childAllBlack = true;
                                            foreach(GraphNode child in n.children)
                                            {
                                                switch (child.state)
                                                {
                                                    case GraphNode.State.White:
                                                        {
                                                            stack.Push(child);
                                                            childAllBlack = false;
                                                        }
                                                        break;
                                                    case GraphNode.State.Gray:
                                                        {
                                                            childAllBlack = false;
                                                            cycled = true;
                                                            cycledNode = child;
                                                            Debug.Log("[AssetBundleGraph] Cycle:" + cycledNode.Name2String());
                                                        }
                                                        break;
                                                    case GraphNode.State.Black:
                                                        break;
                                                }
                                            }

                                            if (childAllBlack)
                                            {
                                                stack.Pop();
                                                n.state = GraphNode.State.Black;
                                            }
                                            else
                                            {
                                                n.state = GraphNode.State.Gray;
                                            }
                                        }
                                    }
                                    break;
                                case GraphNode.State.Black:
                                    stack.Pop();
                                    break;
                            }
                        }
                    }
                    break;
                case GraphNode.State.Black:
                    break;
                case GraphNode.State.Gray:
                    Debug.LogError("[AssetBundleGraph] The node shouldn't be in this state");
                    break;
            }

            if (cycled)
            {
                break;
            }
        }

        if (cycled)
        {
            HashSet<GraphNode> cycledNodes = new HashSet<GraphNode>();

            // 获得循环调用的节点
            while(true)
            {
                GraphNode node = stack.Pop();
                if (node.state == GraphNode.State.Gray)
                {
                    cycledNodes.Add(node);
                }

                if (node == cycledNode)
                {
                    break;
                }
            }

            LinkedList<string> names = new LinkedList<string>();
            HashSet<GraphNode> children = new HashSet<GraphNode>();

            foreach(GraphNode node in cycledNodes)
            {
                foreach(string name in node.names)
                {
                    names.AddLast(name);
                }

                foreach(GraphNode child in node.children)
                {
                    if (!cycledNodes.Contains(child))
                    {
                        children.Add(child);
                    }
                }

                nodes.Remove(node);
            }

            GraphNode newNode = new GraphNode(names, children);
            nodes.Add(newNode);

            foreach (var node in nodes)
            {
                LinkedList<GraphNode> removedList = new LinkedList<GraphNode>();
                foreach (var child in node.children)
                {
                    if (cycledNodes.Contains(child))
                    {
                        removedList.AddLast(child);
                    }
                }

                foreach (var child in removedList)
                {
                    node.children.Remove(child);
                }

                if (removedList.Count > 0)
                {
                    node.children.Add(newNode);
                }
            }
        }

        return cycled;
    }

    public string ToJson()
    {
        JsonData data = new JsonData();
        data.SetJsonType(JsonType.Object);
        Dictionary<GraphNode, int> indexes = new Dictionary<GraphNode, int>();
        int idx = 0;

        data[NODES] = new JsonData();
        data[NODES].SetJsonType(JsonType.Array);
        foreach (var node in nodes)
        {
            data[NODES].Add(new JsonData());
            data[NODES][idx].SetJsonType(JsonType.Object);

            data[NODES][idx][NAMES] = new JsonData();
            data[NODES][idx][NAMES].SetJsonType(JsonType.Array);

            foreach (string name in node.names)
            {
                data[NODES][idx][NAMES].Add(name);
            }
            indexes[node] = idx;

            idx++;
        }

        foreach (var node in nodes)
        {
            int i = indexes[node];

            data[NODES][i][DEPENDENCIES] = new JsonData();
            data[NODES][i][DEPENDENCIES].SetJsonType(JsonType.Array);

            foreach (var child in node.children)
            {
                data[NODES][i][DEPENDENCIES].Add(indexes[child]);
            }
        }

        return data.ToJson();
    }   
}